package string;

public class StringTest_1 {
    public static void main(String[] args) {
        System.out.println("字符串相关力扣题学习~");
    }

    /**
     * 344.反转数组 --easy
     * @param s
     * 双向指针
     */
    public void reverseString(char[] s) {
        int i = 0, j = s.length - 1;
        while(i < j) {
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            i++;
            j--;
        }

        //还可以用异或运算来解决
        //a^a^b = (a^b)^a = b^a^a = b
    }

    /**
     * 541.反转字符串 II --easy
     * @param s
     * @param k
     * @return
     */
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for(int i = 0; i < s.length(); i += 2*k) {
            int start = i;
            int end = Math.min(ch.length - 1, start + k - 1);
            while (start < end) {
                ch[start] ^= ch[end];
                ch[end] ^= ch[start];
                ch[start] ^= ch[end];
                start++;
                end--;
            }
        }
        return new String(ch);
    }

    /**
     * 151.翻转字符串里的单词 --middle
     * @param s
     * @return
     */

    public String reverseWords(String s) {
        //思路先去重多余空格，再整体颠倒一遍，再颠倒每个单词
        //1.去除多余空格 -这里较为复杂 --参考 279.移除元素
        StringBuffer sb = removeExtraSpace(s);
        //2.整体颠倒一遍
        reverseString(sb, 0, sb.length() - 1);
        //3.颠倒每个单词 --快慢指针
        int start = 0;
        int end = start + 1;
        while(start < sb.length()) {
            //找到单词末尾的后一个位置
            while(end < sb.length() && sb.charAt(end) != ' ') {
                end++;
            }
            reverseString(sb, start, end - 1);
            //双指针移动
            start = end + 1;
            end = start + 1;
        }
        return sb.toString();

    }

    private StringBuffer removeExtraSpace(String s) {
        StringBuffer sb = new StringBuffer();
        int start = 0, end = s.length() - 1;
        while (s.charAt(start) == ' ') {
            start++;
        }
        while (s.charAt(end) == ' ') {
            end--;
        }
        while(start <= end) {
            //去中间的多余空格
            char ch = s.charAt(start);
            //当前不是空格，或者当前是空格但前一个字符不是空格
            if(ch != ' ' || (start > 0 && s.charAt(start - 1) != ' ')) {
                sb.append(ch);
            }
            start++;
        }
        return sb;
    }

    private void reverseString(StringBuffer sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }
}
